체육복 (Greedy - 탐욕법)

NOTE

프로그래머스 · 그리디(1차원 배열 상태 탐색) 도난·여벌 상태를 인덱스(=학생 번호)에 델타로 기록하고, 왼쪽→오른쪽으로 단방향 스위핑하며 앞 사람부터 빌려주는 탐욕법. 정렬·Set 없이 O(N).

📝 문제

• 체육복을 도난당한 학생은 여벌이 있는 바로 앞뒤 번호 학생에게만 빌릴 수 있다.
• 체육 수업을 들을 수 있는 최대 학생 수를 구한다.

💡 접근

• 배열 패딩(Array Padding): 인덱스 0과 N+1에 더미 공간을 두면 i-1, i+1 접근 시 IndexOutOfBoundsException을 막는 if (i != 1) 방어 로직이 필요 없다.
• 상태 델타 관리: boolean 배열 여러 개 대신 int 배열 하나에 결핍(도난)은 -1, 잉여(여벌)는 +1로 누적. ‘도난당했지만 여벌이 있는 학생’이 조건문 없이 0(정상)으로 자연스럽게 상쇄된다.

⌨️ 풀이

// 1. 크기 N+2인 패딩 배열 (기본값 0)
int[] state = new int[N + 2];
 
// 2. 상태 증감 기록 (결핍 -1, 잉여 +1)
for (int l : lost) state[l]--;
for (int r : reserve) state[r]++;
 
int answer = N; // 전체에서 못 구한 사람을 뺀다
 
// 3. 그리디 탐색 (단방향 스위핑)
for (int i = 1; i <= N; i++) {
    if (state[i] == -1) {
        // 왼쪽부터 우선 탐색
        if (state[i - 1] == 1) {
            state[i]++;
            state[i - 1]--;
        }
        // 왼쪽이 없으면 오른쪽 탐색
        else if (state[i + 1] == 1) {
            state[i]++;
            state[i + 1]--;
        }
        // 둘 다 없으면 실패
        else {
            answer--;
        }
    }
}

⏱️ 복잡도

• 시간: O(N) — 배열을 한 번만 스위핑. 정렬 불필요.
• 공간: O(N) — 상태 배열.

📎 실전 주의사항 (Pitfalls)

• 탐색 방향과 선택의 일치: 1 → N(왼쪽→오른쪽)으로 돌면 무조건 왼쪽(i-1)부터 빌려야 한다. 오른쪽(i+1)을 먼저 빌리면 다음 차례인 i+1 학생의 자원을 미리 뺏어 전체 최적해가 망가진다.
• 불필요한 정렬·컬렉션 지양: 인덱스 자체가 ‘학생 번호’라는 정렬된 속성을 가지므로 Arrays.sort(), Set, Map이 전혀 필요 없다. O(N)으로 끝내야 하는 유형.

---

🔗 관련

• (Algorithm) 예산 - 핵심 개념 및 특징 정리 — 그리디 계열
• (Algorithm) 60일 계획 - 핵심 개념 및 특징 정리 — 1~20일차 학습 커리큘럼에서 참조하는 문제